Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
Елементи теорії графів
Методичні вказівкидо практичних занять та самостійної роботи з курсу “Дискретна математика”для студентів базового напрямку 6.0915 “Комп’ютерна інженерія”
Затвердженона засіданні кафедриЕлектронних Обчислювальних МашинПротокол № 6 від 21 січня 2003 року
Львів – 2003
Елементи теорії графів : Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладачі: І. Мороз, Р. Попович – Львів: Національний університет “Львівська політехніка”, 2003, 19 с.
Укладачі: Р. Попович, к.т.н., доцент
І. Мороз, асистент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ
Рецензенти: Ємець В. Ф., професор кафедри ЕОМ, д. фіз.-мат. н.
Юрчак І. Ю., доцент кафедри САПР, к. т. н.
Вступ
Зародження теорії графів пов’язують з роботою Ейлера (1736 р.) про Кенігсберзькі мости. Який знайшов критерії існування в графі спеціального маршруту, так званого ейлеревого циклу. Тривалий час цей результат залишався єдиним у теорії графів. Нові результати були отримані лише в XIX ст. в роботах Кіргофа та Келі. Хоча теорія графів виникла більше двох століть тому, її інтенсивний розвиток припадає лише на останні 50-60 років. Цей розвиток завдячує широкому застосуванню графів в теорії автоматів, теорії проектування, економіці, хімії, біології та ін.
Теорія графів, як розділ дискретної математики, з успіхом використовується у задачах керування виробництвом і проектування мереж ЕОМ, при розробці сучасних електронних модулів і при проектуванні фізичних систем, при розв’язуванні задач генетики і вирішенні проблем автоматизованого управління (САПР). Теорія графів є основою математичного забезпечення сучасних систем обробки інформації у прикладній теорії алгоритмів та в інших галузях науки і техніки.
Одним з прикладів ефективного застосування теорії графів в сучасних інформаційних системах є кодування інформації при передачі через канал зв’язку. При цьому ставиться вимога забезпечити виправлення помилок, які виникають внаслідок фізичних завад у каналах зв’язку або пристроях зберігання інформації. Одним з кращих алгоритмів який вирішує дану задачу є алгоритм Вітербі, в основі якого лежить алгоритм пошуку оптимального шляху, що є предметом досліджень в теорії графів.
Далі розглядатимемо деякі елементи теорії графів, які мають загальну форму та можуть бути застосовані при дослідженні об’єктів та систем довільної природи.
1. Основні поняття і операції
1.1. Визначення графу
Предметом перших задач теорії графів були конфігурації, які складаються з точок і ліній, які їх з’єднують. При цьому несуттєво, прямі ці лінії або вони є криволінійними дугами. Важливо лише те, що вони з’єднують дані точки.
Визначення. Розглянемо множину V, яка складається з точок, частина яких з’єднана між собою. Назвемо V множиною вершин, а об’єкт v ( V - вершиною. Граф
G = G(V)
з множиною вершин V - це деяка сукупність пар вигляду
e = (a, b),
де a, b ( V вказують, які пари вершин з’єднані між собою. Відповідно до геометричних уявлень про граф кожна така пара (a, b) називається ребром графу, а „а” і „b” – кінцями ребра. З іншого боку, оскільки
e = (a, b) ( V ( V,
то граф
G(V) ( V ( V.
Визначення. Якщо у визначенні ребра графу не брати до уваги послідовність його кінців, тобто вважати, що
e = (a, b) = (b, a),
то говорять, що e – неорієнтоване ребро. В протилежному випадку e = (a, b) - орієнтоване ребро, в якому „а” – початкова вершина, а „b” – кінцева.
Визначення. Якщо e = (a, b), то говорять, що ребро e інцидентне вершинам „а” і „b”, а вершини „а” і „b” інцидентні ребру e.
1.2. Зображення графів
Визначення. Граф G називається неорієнтованим, якщо кожне його ребро є неорієнтованим. Граф G називається орієнтованим, якщо кожне його ребро є орієнтованим.
Рис. 1.
На рис. 1.а, б, в, е зображені деякі неорієнтовані графи, а на рис. 1.г, д – деякі орієнт...